package ninthweek;

import secondweek.EmptyCollectionException;

public class ArrayHeap<T> extends ArrayBinaryTree<T> implements HeapADT<T> {

    public ArrayHeap() {
        super();
    }

    @Override
    public void addElement(T obj) {
        if (count == tree.length) {
            expandCapacity();
        }
        tree[count] = obj;
        count++;
        modCount++;

        if (count > 1) {
            // 检查当前的插入
            heapModifyAdd();
        }
    }

    private void heapModifyAdd() {
        T temp;
        int next = count - 1;
        temp = tree[next];
        while (next != 0
                && (((Comparable) temp).compareTo(tree[(next - 1) / 2]) < 0)) {
            tree[next] = tree[(next - 1) / 2];
            next = (next - 1) / 2;
        }
        tree[next] = temp;
    }

    @Override
    public T removeMin() throws EmptyCollectionException {
        if (isEmpty()) {
            throw new EmptyCollectionException("ArrayHeap");
        }
        T minElement = tree[0];
        tree[0] = tree[count - 1];
        tree[count - 1] = null;
        heapModifyRemove();
        count--;//当前的空白位置--
        modCount--;
        return minElement;
    }

    /**
     * //删除修改堆结构
     */
    private void heapModifyRemove() {
        T temp;
        // 开始的三个结点
        int node = 0;
        int left = 1;
        int right = 2;

        int next;

        if ((tree[left] == null) && (tree[right] == null))
            next = count;
        else if (tree[right] == null)
            next = left;//右边为null
        else if (((Comparable) tree[left]).compareTo(tree[right]) < 0)
            next = left;
        else
            next = right;
        temp = tree[node];//临时存储  一个需要迁移的位置


        while ((next < count)
                && (((Comparable) tree[next]).compareTo(temp) < 0)) {
            tree[node] = tree[next];
            node = next;
            left = 2 * node + 1;
            right = 2 * (node + 1);
            if ((tree[left] == null) && (tree[right] == null))
                next = count;
            else if (tree[right] == null)
                next = left;
            else if (((Comparable) tree[left]).compareTo(tree[right]) < 0)
                next = left;
            else
                next = right;
        }
        //最后放在node
        tree[node] = temp;

    }

    @Override
    public T findMin() {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");
        return tree[0];
    }

}
